\documentclass[revision]{FPSAC2017}

\articlenumber{4}
\addbibresource{04_Backman_Lenz.bib}


\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}


\usepackage{lipsum}

 


\usepackage{amssymb} 
\usepackage{amsthm}
\usepackage{upref}
\usepackage{graphicx}
\usepackage{color}
\usepackage{url}
\usepackage{paralist}


\usepackage[english]{babel}
 

\usepackage{calc}
 

 
\usepackage{mathrsfs}

\usepackage[all]{xy}
 
\hypersetup{pdfauthor={Spencer Backman, Matthias Lenz},pdftitle={}, 
  pdfkeywords={} }


\newtheorem{Theorem}{Theorem}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Conjecture}[Theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Exercise}[Theorem]{Exercise}
\newtheorem{Question}[Theorem]{Question}
\newtheorem{Example}[Theorem]{Example}


\theoremstyle{remark}
\newtheorem{Remark}[Theorem]{Remark}



 
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\DM}{DM}
\DeclareMathOperator{\relint}{relint}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\vol}{{{vol}}}
\newcommand{\abs}[1]{\left|#1\right|}
\DeclareMathOperator{\image}{image} % image
\DeclareMathOperator{\rank}{rk}
\DeclareMathOperator{\interior}{int}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\diag}

\DeclareMathOperator{\lcm}{lcm} % least common multiple
 

\newcommand{\WLOG}{WLOG} % without loss of generality
\newcommand{\st}{s.\,t.\ } % such that
\newcommand{\ie}{\textit{i.\,e.\ }} % id est
\newcommand{\eg}{\textit{e.\,g.\ }} % exemplum gratum


 

\newcommand{\Ma}{\mathbb{M}^a}
\newcommand{\M}{\mathbb{M}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Acal}{\mathcal{A}}
\newcommand{\Bcal}{\mathcal{B}}
\newcommand{\Ccal}{\mathcal{C}}
\newcommand{\Dcal}{\mathcal{D}}
\newcommand{\Hcal}{\mathcal{H}}
\newcommand{\Ical}{\mathcal{I}}
\newcommand{\Mcal}{\mathcal{M}}
\newcommand{\Zcal}{\mathcal{Z}}
\newcommand{\Pcal}{\mathcal{P}}
\newcommand{\Tcal}{\mathcal{T}}
\newcommand{\Rcal}{\mathcal{R}}
\newcommand{\Jcal}{\mathcal{J}}
\newcommand{\Vcal}{\mathcal{V}}
\newcommand{\Kcal}{\mathcal{K}}
\newcommand{\Wcal}{\mathcal{W}}
\newcommand{\eps}{\varepsilon}
\newcommand{\x}{\vek{x}}
 
 

  


\DeclareMathOperator{\sgn}{{{sgn}}}
\DeclareMathOperator{\ideal}{{{ideal}}}
\DeclareMathOperator{\spa}{{{span}}}
\DeclareMathOperator{\cone}{{{cone}}}
\DeclareMathOperator{\BB}{ \mathbb B}
\newcommand{\II}{ \mathbb I}
\newcommand{\Fcal}{\mathcal F}
\newcommand{\Gcal}{\mathcal G}
\newcommand{\Lcal}{\mathcal L}

\newcommand{\Mfrak}{\mathfrak M}
\newcommand{\cfrak}{\mathfrak c}
\newcommand{\mfrak}{\mathfrak m}

\newcommand{\tutte}{{\mathfrak T}}
\newcommand{\aritutte}{{\mathfrak M}}
\newcommand{\multari}{{\mathfrak m}}
\newcommand{\matroidclass}{{\mathbb M}}

\newcommand{\diff}[1]{\frac{\partial}{\partial #1}}
 
\DeclareMathOperator{\hilb}{{{Hilb}}}
 
 






 
\author{Spencer Backman\addressmark{1}  \and Matthias Lenz\addressmark{2}}
\address{\addressmark{1}Hausdorff Center for Mathematics, 53115 Bonn, Germany\\
\addressmark{2}Universit\'e de Fribourg, D\'epartement de Math\'ematiques, 1700 Fribourg, 
Switzerland \\}

\title[A convolution formula for arithmetic Tutte polynomials]
{A convolution formula for Tutte polynomials of  arithmetic matroids 
and other combinatorial structures}

\received{November 14, 2016}


\revised{April 1, 2017}

\abstract{We generalize the convolution formula for the Tutte polynomial of
 Kook--Reiner--Stanton and Etienne--Las~Vergnas 
 to a more general setting that   
 includes both arithmetic matroids and delta-matroids.
 As   corollaries, we obtain new proofs of two positivity results
 for pseudo-arithmetic matroids and
  a combinatorial interpretation of the arithmetic Tutte polynomial at infinitely many points  in terms of arithmetic flows and colorings.
  We also exhibit connections with a decomposition of Dahmen--Micchelli spaces and lattice point counting in zonotopes.
  Subsequently, we investigate the following problem:
  given a representable arithmetic matroid, when is the arithmetic matroid obtained
  by taking the $k$th power of its multiplicity function again representable?
   Arithmetic matroids of this type arise in the study of CW complexes.
   We also solve a related problem for the Grassmannian.}

\keywords{Tutte polynomial, convolution formula, matroid, arithmetic matroid, delta-matroid, zonotope, nowhere-zero flow, coloring,  Grassmannian, Pl\"ucker coordinates}


\begin{document}


\maketitle






\section{Introduction}

 Matroids are combinatorial structures that capture and abstract the notion of independence.
%
 They were introduced in the 1930s, and since then 
 they have become an important part
 of combinatorics and other areas of pure and applied mathematics.
 The Tutte polynomial is an important matroid invariant. Many invariants of graphs and hyperplane arrangements can be obtained 
 as specializations of the Tutte polynomial 
 \cite{brylawski-oxley-1992}.
%
%  
 Kook--Reiner--Stanton  \cite{kook-reiner-stanton-1999} and Etienne--Las~Vergnas \cite{etienne-las-vergnas-1998}
 found a so-called convolution formula for the Tutte polynomial of a matroid.
 In \cref{Section:ConvolutionFormula}, we will show that their formula holds in a very general setting that includes  
  arithmetic matroids, delta-matroids, and polymatroids.
   As   corollaries, we will obtain new proofs of two positivity results
 for pseudo-arithmetic matroids and
  a combinatorial interpretation of the arithmetic Tutte polynomial at infinitely many points  in terms of arithmetic flows and colorings.
  We will also exhibit connections with a decomposition of Dahmen--Micchelli spaces and lattice point counting in zonotopes.
 This section is based on the preprint \cite{lenz-backman-2016}.
%  
 In \cref{Section:Pluecker}, which is based on the preprint  \cite{lenz-ppcram-2017}
 of the second author, we will discuss the following question:
    given a representable arithmetic matroid, when is the arithmetic matroid obtained
  by taking the $k$th power of its multiplicity function again representable?
   Bajo--Burdick--Chmutov \cite{bajo-burdick-chmutov-2014} have recently discovered that 
   arithmetic matroids of this type arise in the study of flows and colorings on CW complexes.
%   %
% 
 We will also answer the following related question:  
 given an integer $k\ge 2$
 and a vector $v$ of 
 Pl\"ucker coordinates 
% 
 of a point in a real Grassmannian, is the vector 
 obtained by taking the $k$th power of each entry of $v$
% 
 again a vector of Pl\"ucker coordinates?
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
 In \cref{Section:Background}, we will provide some mathematical background.

% 
% 
% 
% 
% 
% 
% 
% 
% 

% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 

 
 
% 
 
% 
 Since 2010, several closely related papers have been presented at FPSAC, \eg on
 arithmetic matroids and their Tutte polynomials \cite{branden-moci-2014,moci-adderio-2013,moci-tutte-2012},
 matroids over a ring \cite{fink-moci-2016},  
 Hopf algebras  of matroids \cite{duchamp-nguyen-krajewski-tanasa-2013},
 flows on cell complexes 
 \cite{beck-kemper-short-2012,duval-klivans-martin-2015}, 
 Tutte invariants for polymatroids
 \cite{cameron-fink-fpsac-short-2016},
 and graded vector spaces arising in the theory of vector partition functions whose Hilbert series
 is captured by the arithmetic Tutte polynomial \cite{lenz-arithmetic-2016}.
 
 
\section{The generalized convolution formula and applications}
\label{Section:ConvolutionFormula} 
 

A \emph{ranked set with multiplicities} is a finite set $M$, together with a rank function 
$\rank : 2^M \to \mathbb{Z}$
that satisfies $\rank(\emptyset)=0$ and a multiplicity function $m : 2^M \to R$, where $R$ denotes a commutative ring with $1$.
% 
 
This setting contains the following combinatorial structures as special cases:
 \begin{compactitem}
  \item \emph{Matroids}: if $\rank$ satisfies the rank axioms of a matroid, $R=\Z$,  and $m \equiv 1$ (\eg \cite{MatroidTheory-Oxley})
% 
  \item \emph{Pseudo-arithmetic matroids}: if $(M,\rank)$ is a matroid and $m : 2^M \to \R_{\ge 0}$ satisfies  certain positivity conditions % 
  \cite{branden-moci-2014}.
  \item \emph{Quasi-arithmetic matroids}: if $(M,\rank)$ is a matroid and $m : 2^M \to \Z_{\ge 0}$ satisfies certain divisibility conditions \cite{branden-moci-2014}.
  \item \emph{Arithmetic matroids}: if $(M,\rank,m)$ is both a pseudo-arithmetic matroid and a quasi-arithmetic matroid  \cite{branden-moci-2014,moci-adderio-2013}.
  \item \emph{Integral polymatroids}: if $\rank$ is the submodular function that defines an integral polymatroid, $R=\Z$ and $m \equiv 1$ (\eg \cite[Chapter~44]{schrijver-co-volB})
  \item \emph{Rank functions of delta-matroids and ribbon graphs:} 
     one can choose $m\equiv 1$ and  $\rank=\rho$, the 
     rank function of an even delta-matroid $(M,\Fcal)$ in the sense of 
     Chun--Moffatt--Noble--Rueckriemen
% 
     \cite{chun-moffat-noble-rueckriemen-2014,krajewski-moffatt-tanasa-2015}.
% 
% 
     Ribbon graphs \cite{bollobas-riordan-2002} define delta-matroids
     in a similar way as 
     graphs define matroids \cite{bouchet-1989,chun-moffat-noble-rueckriemen-2014}.
% 
\end{compactitem}
See \cref{Section:Background} for definitions.
Sometimes, we will write $\rank_M$ and $m_M$ to denote the rank and multiplicity functions of $M$ and we will occasionally write $M$ instead of 
$(M,\rank_M, m_M)$
to denote the
ranked set with multiplicities.


We will show that the convolution formula of  Kook--Reiner--Stanton  \cite{kook-reiner-stanton-1999} and Etienne--Las~Vergnas \cite{etienne-las-vergnas-1998}
 holds in a very general setting. The only thing we require is that restriction and contraction are defined in the usual way:
let $A\subseteq M$. The \emph{restriction} $M|_A$ is the ranked set with multiplicities 
$(A,\rank|_A, m|_A)$, where  $\rank|_A$ and $m|_A$ denote the restrictions of $\rank$ and $m$ to $A$.
% 
% 
 The \emph{contraction} $M / A$ is the
 ranked set with multiplicities
 $(M\setminus A,\rank_{M/A}, m_{M/A})$, where
 $\rank_{M/A}(B):=\rank_M(B\cup A) - \rank_M(A)$ and
  $ m_{M/A}(B) := m_{M}(B\cup A)$ for $B\subseteq M\setminus A$.
% 
% 
% 


 To a ranked set with multiplicities, we associate the \emph{arithmetic Tutte function}
 \begin{equation}
   \aritutte_M(x,y) = \sum_{A\subseteq M} m(A) (x-1)^{\rank(M) - \rank(A)} (y-1)^{\abs{A}-\rank(A)} \in R(x,y) 
 \end{equation}
 and the \emph{Tutte function} $\tutte_M(x,y) = \sum_{A\subseteq M}  (x-1)^{\rank(M)-\rank(A)} (y-1)^{\abs{A}-\rank(A)} \in R(x,y)$.
 As usual, $R(x,y)$ denotes the ring of rational functions in $x$ and $y$ with coefficients in $R$.
 Note that $\aritutte_M(x+1,y+1)$ and $\tutte_M(x+1,y+1)$ are Laurent polynomials in $R[x^{\pm 1},y^{\pm 1}]$.
 If $\rank(A)\le \rank(M)$ and $ \rank(A) \le \abs{A} $ for all $ A\subseteq M $, then both functions are polynomials in $R[x,y]$.
% 


 If $M$ is a matroid, $\tutte_M(x,y)$ is the usual Tutte polynomial.
 As far as we know, the
 Tutte Laurent polynomial $\tutte_M(x+1, y+1)$ of a polymatroid $M$ has not been studied yet. 
% 
 However, other
 Tutte invariants of polymatroids have appeared in the literature
 \cite{cameron-fink-fpsac-short-2016,oxley-whittle-1993}.
% 
 If $M$ is a (quasi/pseudo)-arithmetic matroid,  $\aritutte_M(x,y)$ is the usual
 arithmetic Tutte polynomial \cite{branden-moci-2014,moci-adderio-2013,moci-tutte-2012}.
 The arithmetic Tutte polynomial appears in many different contexts, \eg in the study of the  combinatorics and topology of toric arrangements, 
 of cell complexes, the 
 theory of vector partition functions,  and Ehrhart theory of zonotopes 
 \cite{bajo-burdick-chmutov-2014,lenz-arithmetic-2016,moci-tutte-2012,stanley-1991}.

  If $\rank$ is the rank function of an even delta-matroid
  in the sense of Chun--Moffatt--Noble--Rueckriemen
% 
% 
% 
\cite{chun-moffat-noble-rueckriemen-2014,krajewski-moffatt-tanasa-2015}, then
  $\tutte_M$ is the 
  $2$-variable Bollob\'as--Riordan polynomial of the delta-matroid    
  (see \cite{chun-moffat-noble-rueckriemen-2014} or \cite[(42)]{krajewski-moffatt-tanasa-2015}).
  A special case is the $2$-variable Bollob\'as--Riordan polynomial 
  of a ribbon graph
% 
% 
% 
\cite[p.~22]{krajewski-moffatt-tanasa-2015}.

 



% 
The following result is our  main theorem.
% 
% 
\begin{Theorem}
  \label{Theorem:ArithmeticConvolution}
  Let $(M,\rank,m)$ be a ranked set with multiplicities  (\eg an arithmetic matroid). Let $\aritutte_M$ denote its arithmetic Tutte polynomial
  and let   $\tutte_M$ denote its Tutte polynomial.
  Then
  \begin{equation}
   \aritutte_M(x,y)  = \sum_{A\subseteq M}  \aritutte_{M|_A}(0, y) \tutte_{M/A}(x,0) % 
   = \sum_{A\subseteq M}  \tutte_{M|_A}(0, y) \aritutte_{M/A}(x,0).
   \end{equation}
 \end{Theorem}
Kook, Reiner, and Stanton proved this result in the case where
$(M,\rank)$ is a matroid and $m\equiv 1$ \cite{kook-reiner-stanton-1999}.
Their result also follows easily from
a theorem of Etienne and Las~Vergnas on the decomposition 
of the ground set of a matroid that has a bijective proof \cite[Theorem~5.1]{etienne-las-vergnas-1998}.
It would be interesting to give a bijective proof of our result in the case of arithmetic 
matroids.
 The result of Kook--Reiner--Stanton can also be proved using Hopf algebras
\cite{duchamp-nguyen-krajewski-tanasa-2013,kook-reiner-stanton-1999}.
% 
In the case of even delta-matroids,
% 
our
 theorem specializes to a convolution formula for the $2$-variable Bollob\'as--Riordan polynomial
\cite[Theorem~16(2)]{krajewski-moffatt-tanasa-2015}.

% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
 
\cref{Theorem:ArithmeticConvolution}  provides a new method to prove that the coefficients of the Tutte polynomial of a pseudo-arithmetic matroid are positive
 (\cite[Theorem~5.1]{moci-adderio-2013} and \cite[Theorem~4.5]{branden-moci-2014}).
 \begin{Corollary} % 
 \label{Corollary:PositivityOfCoefficients}
   The coefficients of the  Tutte polynomial of a pseudo-arithmetic matroid are positive integers.
% 
 \end{Corollary}

  
 \begin{Remark}
 \label{Remark:toricvertexdecomposition}
 Let $M$ be an arithmetic matroid that is represented by a list of vectors $X$ in some finitely generated abelian group.
 Let $\Vcal(X)$ denote the set of vertices of the corresponding generalized toric arrangement (for definitions see \cite{moci-tutte-2012}).
   If we set $x=1$, the second expression for $\aritutte_M(x,y)$ in 
    \cref{Theorem:ArithmeticConvolution} is equivalent to 
   \cite[Lemma~6.1]{moci-tutte-2012}, which states that
   \begin{equation}
   \label{eq:arituttevertexdecomposition}
   \aritutte_M(1,y) = \sum_{ p\in \Vcal(X) } \tutte_{M_p} (1,y).
   \end{equation}
% 
   Here,
   $M_p$ denotes the matroid represented by the sublist of $X$ that consists of all elements that define a hypersurface that contains $p$.
% 
   
   Equation \eqref{eq:arituttevertexdecomposition} is related to 
   two decomposition formulas 
   in the theory of splines and vector partition functions: 
   the decomposition of 
   the discrete  space $\DM(X)$ into continuous $\Dcal$-spaces 
   $\DM(X) = \bigoplus_{p \in \Vcal(X)} e_p \Dcal(X_p)$ 
   by Dahmen and Micchelli \cite{dahmen-micchelli-1985b} (see also % 
   \cite[(16.1)]{concini-procesi-book})
% 
   and dually,  the decomposition of the periodic $\Pcal$-spaces by the second author \cite{lenz-arithmetic-2016}.
   These decompositions could be a step towards a bijective proof of our result.
   
   
 \end{Remark}

 
% 



\smallskip
 For two multiplicity functions $m_1,m_2 : 2^M \to R$, we will consider their product $m_1m_2$, defined by 
 $(m_1m_2)(A):= m_1(A)m_2(A)$.
% 
 The following generalization of our main theorem was suggested to us by Luca Moci.
 \begin{Theorem}
 \label{Theorem:GeneralisedMainTheorem}
   Let $(M,\rank,m_1)$ and $(M,\rank,m_2)$ be two ranked sets with multiplicity.
   Then $(M,\rank,m_1  m_2)$ is a ranked set with multiplicity
   and its arithmetic Tutte polynomial is given by the convolution formula
% 
   \begin{equation}
    \aritutte_{(M,\rank,m_1  m_2)}(x,y) 
      = \sum_{A\subseteq M}  \aritutte_{ (M,\rank,m_1)   |_A}(0, y) \aritutte_{(M,\rank,m_2)   /A}(x,0).
% 
% 
   \end{equation}
 \end{Theorem}
 
\cref{Theorem:GeneralisedMainTheorem}  implies a generalized version of the key lemma  (Lemma~2) of \cite{delucchi-moci-2016}.
 
\begin{Corollary}% 
\label{Corollary:PforProduct}
 Let  $(M, \rank)$ be a matroid
 and let  $m_1, m_2 : 2^E \to \R$ be two functions.
% 
% 

 If both $m_1$ and $m_2$ satisfy the positivity axiom (cf.~\eqref{eq:Paxiom}), so does their product $m_1m_2$.
\end{Corollary}



\begin{Remark}
\label{Remark:SquareRepresentable}
    Delucchi--Moci \cite{delucchi-moci-2016} 
    remarked that \cref{Corollary:PforProduct} implies that
    if $(M, \rank,m_1)$ and $(M, \rank,m_2)$ are arithmetic matroids, then 
    $(M, \rank,m_1 m_2)$ is an arithmetic matroid as well. 
    In particular, for an arithmetic matroid $(M,\rank, m)$, the arithmetic matroid $(M,\rank, m^2)$ is again an arithmetic matroid.
% 
    Bajo--Burdick--Chmutov \cite{bajo-burdick-chmutov-2014} discovered that arithmetic matroids of this type arise naturally in the study of
    flows and colorings of CW complexes.
% 
% 
\end{Remark}




% 
\paragraph{Zonotopes.}
It is easy to see that the number of integer points in a polytope is equal to the sum of the number of integer points in the 
interior of all of its faces.
In the case of zonotopes, this statement is equivalent to the specialization
 of \cref{Theorem:ArithmeticConvolution} to $(x,y)=(2,1)$.
\begin{Corollary}
\label{Corollary:TwoOne}
Let $X=(x_1,\ldots, x_N)\subseteq \Z^d$ be a list of  vectors and
let $Z(X):=\{ \sum_{i=1}^N \lambda_i x_i : 0\le \lambda_i \le 1\}$ be the
zonotope defined by $X$.
Then
\begin{align}
  \abs{Z(X)\cap \Z^d} = \aritutte(2,1) &= \sum_{A\subseteq X} \aritutte_{M|_A}(0,1)
  \tutte_{M/A}(2,0) 
  \\
  & =
   \sum_{X \supseteq A \text{ flat}} \aritutte_{M|_A}(0,1)  \tutte_{M/A}(2,0) 
  = \sum_{ F } \abs{ \relint(F)\cap \Z^d },
  \notag
\end{align}
where the last sum is over all faces of $Z(X)$.
\end{Corollary}


 Barvinok and Pommersheim proved a geometric convolution-like formula 
 for the number of integer points in a lattice zonotope. It would be interesting to find a connection with our convolution formula.
 \begin{Theorem}[{\cite[Section~7]{barvinok-pommersheim-short-1999}}]
      Let $X\subseteq \Z^d$ be a  list of $N$ vectors. Then
      \begin{equation}
% 
       \abs{ Z(X) \cap \Z^d } =  \sum_F \vol(F) \gamma(P,F),  
% 
      \end{equation}
 where the sum is over all faces $F$ of the zonotope  and $\gamma(P,F)$ 
 denotes the exterior angle of $F$ at $P$.
 The volume of a face is measured intrinsically with respect to the lattice. 
 
   More specifically, the $k$th coefficient of the Ehrhart polynomial  
   $E_X(q) = q^N \aritutte_X(1 + \frac 1q,1)$ of the zonotope
   is equal to  $ \sum_{F: \dim F=k}  \vol(F) \gamma(P,F) $.
 \end{Theorem}
 
 
 

 
% 
 \paragraph{Flows and colorings.}
 In this subsection we will give a combinatorial interpretation of the evaluation of the arithmetic Tutte polynomial
 of a representable arithmetic matroid
 and a closely related polynomial,  the modified Tutte--Krushkal--Renardy polynomial, at infinitely many integer values 
 in terms of arithmetic flows and colorings.
% 

% 
% 
% 
% 

Br\"and\'en and Moci extended the notions of coloring and flow from graphs 
% 
% 
% 
 to the setting of a finite list of elements from a finitely generated abelian group \cite{branden-moci-2014}.
 These arithmetic flows and colorings are related to our convolution formula in a similar way as
 classical flows and colorings are related to the classical convolution formula \cite[Theorem~2]{kook-reiner-stanton-1999}.
 Arithmetic flows and colorings contain 
 flows and colorings of CW complexes \cite{beck-breuer-godkin-martin-2014,beck-kemper-short-2012}
 as a special case, 
 when the list of vectors is 
 taken to be the  boundary operator of a CW complex   
 \cite[Lemma~4]{delucchi-moci-2016}.
  

We briefly review the setup of Br\"and\'en and Moci. 
Let $G$ be a finitely generated abelian group.  
Let $X$ 
% 
be a finite list (or sequence) of elements of $G$. % 
We call $\phi \in \Hom(G, \mathbb{Z}_q)$ a \emph{proper arithmetic $q$-coloring} if $\phi(x) \neq 0$ for all $x \in X$. 
We denote the number of proper arithmetic $q$-colorings of $X$ by $\chi_{X}(q)$.
% 
% 
% 
A \emph{nowhere zero $q$-flow} on $X$ 
is a function $\psi : X \to \Z_q \setminus \{0\}$ \st
 $\sum_{x \in X} \psi(x) x = 0$ in $G/qG$.
 We denote the number of such functions by $\chi^*_{X}(q)$.

For $B\subseteq X$, let $G_B$ denote the torsion subgroup of the quotient
$G / \left\langle \{ x : x\in B \} \right\rangle$ and let $m(B):=\abs{G_B}$.
% 
 Let $\lcm(X):=\lcm\{ m(B) : B \subseteq X \text{ basis}\}$.
 We define the following two subsets of the set of   positive integers:
\begin{align}
 \mathbb{Z}_M(X) &:= \{q\in \Z_{>0} : \gcd(q, \lcm(X))=1\} 
 \\
 \text{and }
 \mathbb{Z}_A(X) &:= \{q\in \Z_{>0} : q G_B = \{0\} \text{ for all bases } B \subseteq X \}.
\end{align}


Given a list of vectors $X$ that represents an arithmetic matroid $(M,\rank,m)$, we let $\aritutte_X(x,y)$ 
denote the arithmetic Tutte polynomial $\aritutte_{(M,\rank,m)}(x,y)$. 
Furthermore, we let $\aritutte_{X^2}(x,y)$ denote the arithmetic Tutte polynomial of $(M,\rank,m^2)$. 
We recall that by \cref{Corollary:PforProduct} (or by \cite{delucchi-moci-2016}),  $(M,\rank,m^2)$ is indeed an arithmetic matroid.
% 
% 
 The polynomial $\aritutte_{X^2}(x,y)$ has a special significance 
 for arithmetic matroids that arise from CW complexes.
 In this case, the \emph{modified $j$th Tutte--Krushkal--Renardy polynomial}, that was introduced in \cite{bajo-burdick-chmutov-2014}, 
 is equal to
 the arithmetic Tutte polynomial $\aritutte_{X^2}(x,y)$, where $X$ is the list of vectors obtained from the $j$th boundary operator
 \cite[Section~4]{delucchi-moci-2016}.
% 
% 
% 
% 
% 
% 
 




\begin{Theorem}[Br\"and\'en--Moci, \cite{branden-moci-2014}]
\label{Theorem:BrandenMociFlowsColourings}
Let $G$ and $X$  be as above.
\begin{align}
\text{If $q \in \mathbb{Z}_A(X)$, then 
 } \chi_{X}(q) &= (-1)^{\rank(X)}q^{\rank(G) - \rank(X)} \aritutte_X(1-q,0)
\\
\text{and }
\chi^*_{X}(q) &= (-1)^{\abs{X} - \rank(X)} \aritutte_X(0,1-q).
\displaybreak[2]
\\
\text{If $q \in \mathbb{Z}_M(X)$, then 
}
\chi_{X}(q) &= (-1)^{\rank(X)}q^{\rank(G)-\rank(X)} \tutte_X(1-q,0) \\
\text{and } \chi^*_{X}(q) &= (-1)^{\abs{X}-\rank(X)} \tutte_X(0,1-q).
\end{align}
\end{Theorem}

\begin{Example}
  Let $X=((2,0),(-1,1),(1,1))$.
% 
% 
% 
Then $\lcm(X)=2$,  
         $ \mathbb{Z}_M(X) = \{1,3,5,7,\ldots\} $, and
         $ \mathbb{Z}_A(X) = \{2,4,6,8,10,12,\ldots\} $.
% 
% 
% 
	 The polynomials are
	 $\chi_X(q)|_{\mathbb{Z}_A(X)}= q^2 - 4q + 4$,
	 $\chi_X(q)|_{\mathbb{Z}_M(X)}= q^2 - 3q + 2$,
	 $\chi_X^*(q)|_{\mathbb{Z}_A(X)}= 2q-3$, and
	 $\chi_X^*(q)|_{\mathbb{Z}_M(X)}= q-1$.
% 
	 Hence there are two proper arithmetic $3$-colorings ($[1,0]$ and $[2,0]$)
	 and two nowhere zero  $3$-flows ($[1,1,2]$ and $[2,2,1]$).
\end{Example}

 

% 

 
 
Let $A\subseteq X$.
We denote the sublist of $X$ that is indexed by $A$ by $X|_A$ (restriction) 
and the projection of $X|_{X\setminus A}$ to $G/A := G/\langle \{x : x\in A\}\rangle$ by $X/A$ (contraction).
 
 \begin{Corollary}
 \label{Corollary:squared}
  Let $G$ and $X$ be as above and $p,q  \in \mathbb{Z}_A(X)$. Then  
  the following equation holds for the modified $j$th Tutte--Krushkal--Renardy polynomial $\aritutte_{X^2}(1-p,1-q)$:
% 
% 
% 
\begin{equation}
     \aritutte_{X^2}(1-p,1-q) =
  p^{\rank(G)-\rank(X)}(-1)^{\rank(X)}\sum_{ A\subseteq X}(-1)^{|A|}\chi^*_{X|_A}(q) \chi_{X/A}(p).
\end{equation}
% 
 \end{Corollary}
 
 
 \begin{Corollary}
 \label{Corollary:FlowsColourings}
  Let $G$ and $X$  be as above, $p \in \mathbb{Z}_A(X)$ and $q \in \mathbb{Z}_M(X)$. Then  
   
% 
\begin{equation}
\aritutte_{X}(1-p,1-q)
   = p^{\rank(G)-\rank(X)}(-1)^{\rank(X)}
   \sum_{A\subseteq X}(-1)^{|A|}\chi^*_{X|_A}(q) \chi_{X/A}(p).
\end{equation}


The same statement holds if we instead take  $p \in \mathbb{Z}_M(X)$ and $q \in \mathbb{Z}_A(X)$.
 \end{Corollary}
 
 
\begin{Corollary}
 Let $\Acal$ be an arithmetic matroid that arises from   a labeled graph $((V,E),\ell)$.
 Then 
 we can interpret the arithmetic Tutte polynomial $\aritutte_\Acal$ in terms of classical flows and arithmetic colorings, or vice versa, \ie
\begin{equation}
 \aritutte_{\Acal}(1-p,1-q) = 
 p^{\rank(G)-\rank(E)}(-1)^{\rank(E)}\sum_{A\subseteq E}(-1)^{|A|}\chi^*_{X|_A}(q) \chi_{\Gcal /A}(p)
\end{equation} 
 for any $p\in \Z$ and $q\in \Z_A(X)$. For $p\in \Z_A(X)$ and any $q\in \Z$ we obtain
\begin{equation}
 \aritutte_{\Acal}(1-p,1-q) = 
 p^{\rank(G)-\rank(E)}(-1)^{\rank(E)}\sum_{A\subseteq E}(-1)^{|A|}\chi^*_{\Gcal|_A}(q) \chi_{X/A}(p).
\end{equation} 
Here, $X$ denotes a list of vectors that represents the arithmetic matroid $\Acal$.
 $\chi^*_{\Gcal}$ and $\chi_{\Gcal}$ denote the  classical   flow polynomial and chromatic polynomial of the graph $\Gcal = (V,E)$, respectively.
\end{Corollary}
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 



\section{Representability of arithmetic matroids and powers of Pl\"ucker coordinates}
\label{Section:Pluecker}
 As explained in \cref{Remark:SquareRepresentable}
 (see also  \cref{Corollary:squared}), 
 it is interesting to consider the arithmetic matroid
 $\Acal^2 := (E, \rank, m^2)$, given an arithmetic matroid $\Acal=(E,\rank,m)$.
% 
 One can ask whether $\Acal^2$ is representable, if $\Acal$ is representable.
% 
% 
% 
 This is in general not the case.
% 
% 
% 
% 
% 
% 
% 
% 
% 
 
 \begin{Theorem}
\label{Theorem:NonRegularNonRepresentable}
 Let $\Acal = (E, \rank, m)$ be an arithmetic matroid.
 Suppose that $\Acal$ is representable and the matroid $(M, \rank)$ is non-regular.
 Let $k\ge 2$ be an integer.
 Then $\Acal^k:= (E, \rank, m^k)$ is not representable.
\end{Theorem}
The proof uses the Pl\"ucker relations and the fact that every non-regular matroid that is representable over $\Q$ contains the  uniform matroid $U_{2,4}$ as a minor.


For regular matroids, the situation is quite complicated and representability no longer depends only on the underlying matroid, but 
also on the multiplicity function.
% 
 However, we are able to prove the following statement. A stronger result can be found in \cite{lenz-ppcram-2017}.

 \begin{Proposition}
 \label{Proposition:LabelledGraphsSquareable}
    Let  $\Acal(\Gcal,\ell)$ be an arithmetic matroid defined by a labeled graph $(\Gcal,\ell)$. Let $k\ge 0$ be an integer and 
    let $\Acal(\Gcal,\ell)^k$ denote the arithmetic matroid obtained from $\Acal(\Gcal,\ell)$ by taking the $k$th power of its
    multiplicity function.
% 
    Then
    $\Acal(\Gcal,\ell)^k =  \Acal(\Gcal,\ell^k)$, where $\ell^k(e):= (\ell(e))^k$ for $e\in E$. 
    In particular, the arithmetic matroid $\Acal(\Gcal,\ell)^k$ is representable by a list of vectors.
% 
% 
% 
% 
% 
% 
% 
% 
  \end{Proposition}



 
 
  
  Let $X$ be a  matrix with integer entries and let 
  $\Acal= (M_X, \rank_X, m_X)$ denote the arithmetic matroid represented by $X$.
  Recall that for a basis $B\subseteq X$, $m_X(B)= \abs{\det(B)}$.  
  If we look for a matrix $X_k$ that only satisfies $m_{X_k}(B) = m_X(B)^k$ for all bases
  and does not necessarily represent $\Acal^k$, 
  then
  the situation is much simpler, as we can see from the following theorem.
  
 \begin{Theorem}
 \label{Theorem:NonRegularMatrices}
  Let $X$ be a $(d\times N$)-matrix of full rank $d \le N$ with entries in $\R$.
% 
% 
  Let $k\neq 1$ be a non-negative real number.
% 
  Then $X$ represents a regular matroid if and only if the following condition is satisfied:
% 
  there is a $(d\times N$)-matrix $X_k$ with entries in $\R$ \st
  for each maximal minor $\Delta_I(X)$, indexed by $I\in \binom{[N]}{d}$, $\abs{\Delta_I(X)}^k = \abs{\Delta_I(X_k)}$
  holds.
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
 If $k$ is a non-negative integer, then the same statement holds over any ordered field $\K$.
% 
% 
 \end{Theorem}
% 
% 
 
   If $d\le N$, the maximal minors of a $(d\times N)$-matrix $X$ with entries in a field $\K$ are known as the  \emph{Pl\"ucker coordinates}
  of the space spanned by the rows of $X$ (\eg \cite[Section~2.4]{OrientedMatroidsBook}).
  The    \emph{Grassmannian} $\Gr_\K(d,N)$, \ie the set of all $d$-dimensional subspaces of $\K^N$, 
  is an important example of an   algebraic variety.
% 
  One of its elements is uniquely determined by its Pl\"ucker coordinates (up to a scalar, non-zero multiple).
  This yields an embedding of the Grassmannian into the $(\binom{N}{d}-1)$-dimensional projective space.  
  The image is described by a set of polynomial equations, the so-called Grassmann--Pl\"ucker relations. 
% 
  Hence \cref{Theorem:NonRegularMatrices} answers the following question:
% 
   given 
   a non-negative real number $k\neq 1$ and
   a vector of Pl\"ucker coordinates  
   $ (\xi_{i_1\ldots i_d})_{1\le i_1 < \ldots < i_d \le N}$ describing a point in $\Gr_\R(d,N)$, 
   when does  $( \pm \xi_{i_1\ldots i_d}^k)_{1\le i_1 < \ldots < i_d \le N}$ correspond to a point in $\Gr_\R(d,N)$?
% 
 


\begin{Example}
\label{Example:NonSquareableC4}
% 
% 
Let
\begin{equation*}
    X =
  \begin{pmatrix}
    1 & 1 & 2 & 1  \\
    0 & 2 & 1 & 2  \\
    0 & 0 & 3 & 2
  \end{pmatrix}
\quad\text{and}\quad
% 
 X_2 =
\begin{pmatrix}
 1 & 1 & 1 & 1 \\
 0 & 4 & 4 & 0 \\
 0 & 0 & 9 & 4 
% 
\end{pmatrix}.
\end{equation*}
% 
% 
% 
 Let $\Acal$ denote the arithmetic matroid that is represented by $X$. Then $X_2$ represents the arithmetic matroid $\Acal^2$.
\end{Example}
 

 
 \section{Background}
 \label{Section:Background}
 
% 
\paragraph{Matroids and arithmetic matroids}
% 
A \emph{matroid} is a pair $(M,\rank)$, where $M$ denotes a finite set
and the rank function $\rank : 2^M \to \Z_{\ge 0}$ satisfies certain axioms 
(see \cite{MatroidTheory-Oxley}).
% 
% 
% 
% 
% 
% 
% 
 Let $\K$ be a field.
 A % 
 matrix $X$ with entries in $\K$ 
% 
% 
% 
 defines a matroid in a canonical way:
 $M$ is the set of columns of the matrix and the rank function 
 is the rank function from linear algebra.
 A matroid that  can be represented 
 in such a way is called \emph{representable over $\K$}.
% 
  A matroid is \emph{regular} if and only if it can be represented by a totally unimodular matrix. 
 This is equivalent to being representable over any field.
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 

% 
% 
\begin{Definition}[D'Adderio--Moci, Br\"and\'en--Moci
\cite{branden-moci-2014,moci-adderio-2013}]
 An \emph{arithmetic matroid} is a triple $(M, \rank, m)$, where
 $(M, \rank)$ is a matroid and $m : 2^M \to \Z_{\ge 0}$ is the
 \emph{multiplicity function}
 that satisfies certain axioms:
% 
 \begin{compactitem}
   \item[(P)]  Let $R\subseteq S\subseteq M$. The set $[R,S]:=\{A: R\subseteq A\subseteq S\}$ is called a \emph{molecule} 
 if $S$ can be written as the disjoint union $S=R\cup F_{RS}\cup T_{RS}$ and for each $A\in [R,S]$,
 $\rank(A)= \rank(R) + \abs{A \cap F_{RS}}$ holds.
% 
 For each molecule   $[R,S] \subseteq M$, the following inequality holds 
 \begin{equation}
  \label{eq:Paxiom}
  \rho(R,S) := (-1)^{\abs{T_{RS}}} \sum_{A\in [R,S]} (-1)^{\abs{S} - \abs{A} } m(A) \ge 0.
 \end{equation}
  \item[(A1)]  For all $A \subseteq M$ and $e \in M$:
if $\rank(A \cup \{e\}) = \rank(A)$, then $m(A \cup \{e\})| m(A)$.
Otherwise $m(A) | m(A \cup \{e\})$.
  \item[(A2)]  If $[R, S]$ is a molecule, then $m(R)m(S) = m(R \cup F ) m(R \cup T )$.
  \end{compactitem}
% 
 A \emph{pseudo-arithmetic matroid} is a triple $(M, \rank, m)$, where
 $(M, \rank)$ is a matroid and $m : 2^M \to \R_{\ge 0}$ satisfies (P).
% 
 A \emph{quasi-arithmetic matroid} is a triple $(M, \rank, m)$, where
 $(M, \rank)$ is a matroid and $m : 2^M \to \Z_{\ge 0}$ satisfies (A1) and (A2).
% 
\end{Definition}

 The prototypical example of an arithmetic matroid 
 is defined by a list of vectors $X$ in $\Z^d$.
 In this case, for a sublist   $S$ of $d$ vectors that form a basis, we have $m(S) = \abs{\det(S)}$
 and in general $m(S) := \abs{\left\langle x \in S\right\rangle_\R \cap \Z^d / \left\langle x \in S\right\rangle_\Z}$. 
% 
 As quotients of $\Z^d$ are in general not free groups, the following definition will use a slightly more general setting.
 

\begin{Definition}
 Let $\Acal = (M, \rank, m)$ be an arithmetic matroid.
 Let $G$ be a finitely generated abelian group and $X $ a finite list of elements of $G$ that is indexed by $M$.
 For $A\subseteq M$, let  $G_A$ denote the maximal subgroup of $G$ \st $ \abs{G_A / \left\langle A \right\rangle}$ is finite.
% 
  $X$ is called a \emph{representation} of $\Acal$ if the matroid defined by $X$ is isomorphic to $(M,\rank)$ 
  and 
  $m(A) = \abs{G_A / \left\langle A \right\rangle}$.
% 
  The arithmetic matroid $\Acal$ is called \emph{representable} if it has a representation $X$.
\end{Definition}

 
% 
% 
 
 Given a representation $X\subseteq \Z^d$ of an arithmetic matroid, it is easy to calculate its 
 multiplicity function \cite[p.~344]{moci-adderio-2013}:
 let $A\subseteq X$, then 
        \begin{equation}
 \label{eq:dependentmultiplicity}
 m(A) = \gcd( \{ m(B) : B \subseteq A \text{ and  } \abs{B} = \rank(B) = \rank(A) \}).
 \end{equation}
 If $A$ is independent, then  $m(A)$ is the greatest common divisor of all minors of size $\abs A$ of the matrix $A$
 (cf.~\cite[Theorem~2.2]{stanley-1991}).
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 

 
 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 
% 

% 
 



% 
 \paragraph{Arithmetic matroids defined by labeled graphs}
   \label{Subsection:LabelledGraphs}
   A \emph{labeled graph} is a graph $\Gcal=(V,E)$ together with a map $\ell : E \to \Z_{\ge 1}$.
   The graph $\Gcal$ is allowed to have multiple edges, but no loops.
   The set of edges is partitioned into a set $R$ of \emph{regular edges} and a set $D$ of \emph{dotted edges}.
% 
% 
% 
   Such a graph defines a graphic arithmetic matroid  \cite{moci-adderio-flow-2013}.
   Its definition extends the usual construction of the matrix representation of a graphic matroid
   by the oriented incidence matrix:
% 
   let $ V = \{v_1,\ldots, v_n\}$. We fix an arbitrary orientation $\theta$ of $E$ \st each edge $e\in E$ can be identified with an ordered pair $(v_i,v_j)$.
   To each edge $e = ( v_i , v_j )$, we associate the element $x_e \in \Z^n$ defined as the vector
   whose $i$th coordinate is $-\ell(e)$ and  whose $j$th coordinate is $\ell(e)$.
    Then we define the  list $X_R := (x_e)_{e\in R}$
% 
% 
% 
   and the group
   $ G := \Z^n / \langle \{ x_e : e \in D \} \rangle$. We denote by $\Acal(\Gcal,\ell)$
   the arithmetic matroid represented by the 
     projection of  $X_R$ to $G$.
% 
% 
% 
% 
% 
% 

\paragraph{Delta-matroids and the Bollob\'as--Riordan polynomial.}
\label{Subsection:DeltaMatroidsDefinition}
% 
A \emph{delta-matroid} $D$ is a pair $(E,\mathcal{F})$, where  $E$ denotes a finite set and $ \emptyset \neq \mathcal{F}\subseteq 2^E$ satisfies 
the \emph{symmetric exchange axiom}: for all $S,T\in \mathcal{F}$, if there is an element $u\in S\triangle T$, then 
there is an element $v\in S\triangle T$ such that $S\triangle \{u,v\}\in \mathcal{F}$.   
The elements of $\mathcal{F}$ are called \emph{feasible sets}.
% 
% 
If the sets in $\Fcal$ all have the same cardinality, then 
$(E,\Fcal)$ satisfies the basis axioms of a matroid.
% 
% 
Let $D=(E,\Fcal)$ be a delta-matroid
 and let $\mathcal{F}_{\max}$ and $\mathcal{F}_{\min}$ be the set of feasible sets of maximum and minimum cardinality, 
respectively.  
% 
% 
Define $D_{\max}:=(E,\mathcal{F}_{\max})$ and  $D_{\min}:=(E,\mathcal{F}_{\min})$ to be the 
 \emph{upper matroid} and  \emph{lower matroid} for $D$, respectively  \cite{bouchet-1989}.
% 
Let $
\rank_{\max}$ and $\rank_{\min}$ denote the corresponding rank functions.
% 
% 
In  \cite{chun-moffat-noble-rueckriemen-2014}, the following delta-matroid rank function was defined:
% 
$\rho(D) :=  \frac{1}{2}( \rank_{\max}(D)  +   \rank_{\min}(D) )$, 
and
% 
  $\rho(A) :=   \rho(D|_A) \text{ for } A \subseteq E$.
% 
This can be used to define
 the \emph{(2-variable) Bollob\'as--Riordan polynomial} 
% 
%
$\tilde{R}_D(x,y) :=  \sum_{A\subseteq E}  (x-1)^{\rho(E)-\rho(A)}(y-1)^{|A|-\rho(A)}$.
%
% 
% 
If $D$ is a matroid, then  $\rho$ is its rank function.
Note that the delta-matroid rank function $\rho$ is different from Bouchet's birank \cite{bouchet-1989}.
  A delta-matroid is even
 if all feasible sets have the same parity. A ribbon graph defines an even delta-matroid if and only if 
it is orientable.

\acknowledgements{Matthias Lenz was supported by a Swiss Government Excellence Scholarship for Foreign Scholars 
and subsequently by a
fellowship within the postdoc program of the German Academic Exchange Service 
(DAAD).% 
}


\printbibliography

\end{document}
